I. Field of the Invention
The present invention relates to the field of digital computation and more particularly to multiplication of binary numbers.
II. Related Art
In a 1979 paper, An 0(n) Parallel Multiplier with Bit-Sequential Input and Output, Chen and Willoner described a parallel multiplier which operates in time 0(n) where n is the maximum of the lengths of the multiplier and the multiplicand, both expressed in binary fixed point notation. The paper disclosed a logic circuit of 2n modules with each module having five inputs and three outputs, each being slightly more complex than a full adder. Chen and Willoner disclose a method in which the input is required bit-sequentially, and the output is generated bit-sequentially but in which the circuitry results in the outputs being kept in place. This is necessary to provide the parallel output and requires bit by bit multiplexing to obtain a serial representation of the product.
U.S. Pat. No. 4,135,249 to Irwin for A Signed Double Precision Multiplication Logic describes a multiplier with a plurality of identical multiplication cells forming partial products summed in largely identical summation cells to form the final product. Each multiplication cell stores a multiplier bit and contains a stage of a multiplicand shift register and a stage of a timing waveform shift register. Both the signed multiplication logic of Irwin and the disclosure by Chen and Willoner differ from the invention described herein relative to the required adder precision. In Chen and Willoner, a 32 bit multiplier requires two 32 bit adders. The disclosure in U.S. Pat. No. 4,135,249 to Irwin and in related U.S. Pat. No. 3,947,670, also to Irwin, would require two 32 bit adders in the case of a 32 bit multiplier. The invention described herein provides for dividing the result by two during every iteration so that only about half the adder precision, i.e., N/2+1, is required. Thus, only two 17 bit adders would be necessary.
U.S. Pat. No. 3,016,195 to Hamburgen also discloses a binary multiplier. Unlike the multipliers of Irwin, Hamburgen uses n cells where n is the number of bits in the multiplicand and the multiplier rather than 2n cells as disclosed both by Chen and Irwin. However, Hamburgen discloses a method significantly different from that described herein.